package 代码随想录.单调栈.下一个更大元素I;

import java.util.*;

public class LeetCode496 {
    //暴力法
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int j = 0;
            //找到和nums1[i]相等的元素位置
            while (j < n && nums1[i] != nums2[j]) {
                j++;
            }
            //准备往后找比它大的值
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                k++;
            }
            if (k < n) { //找到了
                res[i] = nums2[k];
            } else {//没找到
                res[i] = -1;
            }
        }
        return res;
    }

    //单调栈
    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] res = new int[m];
        //先单独处理nums2,找到每个元素的下一个更大元素，存储map中：{当前元素->下一个更大元素}
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //这里栈中存储的是值，每日温度存是方便计算相差多少天
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                Integer pop = stack.pop();
                map.put(pop, nums2[i]);
            }
            stack.push(nums2[i]);
        }
        //此时栈中都是未找到下一个更大元素的值，直接全部赋值为-1即可。
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            map.put(pop, -1);
        }
        for (int i = 0; i < m; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        LeetCode496 code496 = new LeetCode496();
//        int[] ints = code496.nextGreaterElement(nums1, nums2);
        int[] ints1 = code496.nextGreaterElement1(nums1, nums2);
//        System.out.println(Arrays.toString(ints));
        System.out.println(Arrays.toString(ints1));

    }
}
